Batch 2 - Class 56 - Game of Life
Preclass Exercise:
Solve the following using mathematical induction.
- (Cornell) Natives Puzzle - Natives in a certain colony have a myth that there is a certain disease signaled by a blue mark on their forehead. If they find out that they have the disease, they must declare it the very next day in the townhall meeting, and leave the colony. However, no one else tells others if they have a blue mark out of courtesy. One day, a foreigner comes in, and tells the whole society that he has seen at least one blue mark in the colony. What will happen?
- We have done this problem before - now we can solve it using induction
- What happens if all the natives have a blue mark on their forehead? And why does a foreigner telling them help, since they already know the fact being stated?
- (Cornell) Pirates Puzzle - There are 13 pirates, who find a pot of cold coins. Pirates are ranked by hierarchy. The leader must propose a distribution, and others must vote. A tie results in the proposal being passed. Otherwise, the leader/proposer is killed, and the next leader proposes a distribution. Pirates are greedy, but given all equal, they don't want to kill their fellow pirates because it makes the gang weaker. What is the final distribution?
- Solve for small number of pirates - see the pattern
- Form a hypothesis
- Base case is already proven by now
- Prove the induction step
- Answer: The leader keeps all the coins and everyone else gets nothing.
Attendance: Tishyaa, Smiti, Muskaan, Anisha, Nandini, Shubham, Diya
Class Notes:
Conway's Game of Life
Rules of the game:
- Three are number of dead squares and a few live ones at beginning of the game
- A live square with 0,1 or more than 4 neighbors dies in the next generation due to isolation/crowding. A live square with 2 or 3 neighbors lives on
- A dead square with 3 neighbor cells becomes alive in the next generation
See a video: https://www.youtube.com/watch?v=C2vgICfQawE
Let kids try out the following patterns and what happens. Let kids try out patterns on left, and use a computer program to do the ones on the right. https://bitstorm.org/gameoflife/
Conway conjectured that all such patterns must be finite, and floated a $50 reward to prove or disprove.
What do you think happened? Try out the Gosper Glider Gun
Applications
- People believe one can use this to understand life: In 2010, Andrew Wade created the first life simulator demonstrating two objects "reproducing" a third one, after 34 million steps ("Gemini") https://www.youtube.com/watch?v=A8B5MbHPlH0
- Shows that local action and local rules are enough to generate complex behavior, including reproduction
- Can be used in robots - specify local rules, and there is no need to have an overview of the world
- Think about how we navigate
- Music synthesizer - http://hujackus.altervista.org/conwaymatrix/
- https://vimeo.com/3328851 and if you want to try the sequencer out, https://grantmuller.com/game-of-life-sequencer-bank-demo/
Homework:
- (Moscow - 197) A complete set of dominos is as shown below. If you place all the 28 tiles in a continuous chain (adjacent ends of the tiles must match) so that 5 dots are at one end, how many dots will be at the other end?
- There are 6 people in a room. Each pair of people either mutually know each other or not. Prove that there are at least three people, who either all know each other, or none of whom know each other.
References:
The Colossal Book of Mathematics, by Martin Gardner
The Moscow Puzzles, by Boris A. Kordemsky